# -*- coding: utf-8 -*-
class HeapSort:
	'''Algoritmo de ordenação por selecção.'''

	def __init__(self, unsortedList):
		'''Construtor da classe
		@param unsortedList -> lista que vai ser ordenada
		'''
		self.unsortedList = unsortedList
		self.heapsort(unsortedList)

	def left(self,i):
		'''Função que que define qual a posição descendente à esquerda na pilha.
		@param i -> Posição da pilha.
		'''

		self.i = i
		return (2*i)

	def right(self,i):
		'''Função que que define qual a posição descendente à direita na pilha.
		@param i -> Posição da pilha.
		'''

		self.i = i
		return ((2*i)+1)

	def build_max_heap(self,unsortedList):
		'''Função que constroi uma pilha máxima chamando a função max_heapify.
		Começa no meio da pilha menos 1 (pois o elemento descendente da direita
		é o dobro da sua posição mais 1) e vai de crescendo até à primeira posição.
		@param unsortedList -> lista para a construção da pilha(heap)
		'''

		self.unsortedList = unsortedList
		for i in range( ((len(unsortedList)-1) / 2), -1, -1):
			self.max_heapify(unsortedList,i,len(unsortedList)-1)

	def max_heapify(self,heap,i,heapSize):
		'''Função que compara cada posição da pilha com o seu descendente equerdo e direito
		trocando o valor caso necessário para que o maior valor fique no topo.
		@param heap -> Pilha para passar o maior elemento para a raiz.
		@param i -> Posição da pilha a para começar as comparações.
		@param heapSize -> Tamanho actual da pilha.
		'''

		self.heap = heap
		self.i = i
		self.heapSize = heapSize
		l = self.left(i)
		r = self.right(i)
		if (l <= heapSize) and (heap[l] > heap[i]):
			largest = l
		else:
			largest = i
		if ((r)<= heapSize) and (heap[r] > heap[largest]):
			largest = r
		if largest != i:
			heap[i], heap[largest] = heap[largest], heap[i]
			self.max_heapify(heap,largest,heapSize)

	def heapsort(self,unsortedList):
		'''Define o tamanho da pilha, chama a função build_max_heap enviando a lista e
		vai trocando o último elemento da lista com o primeiro(que já é o maior) diminuindo 1 no tamanho da pilha
		e chamando a função max_heapify até ficar sem pilha.
		@param unsortedList -> lista que vai ser ordenada.
		'''
		self.unsortedList = unsortedList
		heapSize = len(unsortedList) - 1
		self.build_max_heap(unsortedList)
		for i in range(heapSize,0,-1):
			unsortedList[i], unsortedList[0] = unsortedList[0], unsortedList[i]
			heapSize = heapSize - 1
			self.max_heapify(unsortedList,0,heapSize)